package zwp.exercise.intereview.base.sort;

import java.util.Arrays;

/**
 * @Author zwp14
 * @create 2024/6/27 20:34
 * @description 冒泡排序 -- 稳定排序
 * 依次比较两个相邻的元素,如果前者a[i]比后者a[i+1]大,则进行两两交换,直至最大的数排在末尾,完成一轮冒泡
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] a = {5, 9, 7, 4, 1, 3, 2, 8};
//        int[] a = {1, 2, 3, 4, 5, 7, 8, 9};
        System.out.println("未进行冒泡排序之前:" + Arrays.toString(a));
//        int[] bubble = bubble(a);
//        System.out.println("冒泡排序之后:" + Arrays.toString(bubble));
        //会这个就可以
//        int[] bubble2 = bubble2(a);
//        System.out.println("冒泡排序之后:" + Arrays.toString(bubble2));

        //最优解
        int[] bubble3 = bubble3(a);
        System.out.println("冒泡排序之后:" + Arrays.toString(bubble3));
    }


    private static int[] bubble3(int[] a) {
        int n = a.length - 1;
        int count = 0;
        while (true) {
            int last = 0;
            for (int i = 0; i < n; i++) {
                if (a[i] > a[i + 1]) {
                    count++;
                    exchange(a, i);
                    last = i;
                    System.out.println("第" + count + "轮次冒泡:" + Arrays.toString(a));
                }

            }
            n = last;
            if (last == 0) {
                break;
            }
        }
        return a;

    }


    private static int[] bubble2(int[] a) {
        int count = 0;

        for (int i = 0; i < a.length - 1; i++) {

//            //本方法共49次执行,对于已经将最大的数字排序到最后,就无需再进行比较,应当减去一次,
//            //内圈减去一次,相当于总次数减去7次
//            for (int j = 0; j < a.length -1; j++) {
//                if (a[j]>a[j+1]){
//                    exchange(a,j);
//                }
//                count++;
//            }

            //本方法共28次执行,内圈减去i次,对应有9.8.7已经按照从小到大排序在末尾了
            //如果在循环没有结束之前,已经有序了,也就是没有数字再次发生交换,就没必要再进行下一轮冒泡
//            for (int j = 0; j < a.length -1 -i; j++) {
//                if (a[j]>a[j+1]){
//                    exchange(a,j);
//                }
//                count++;
//            }

            boolean isExchange = false;
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    exchange(a, j);
                    isExchange = true;
                }
                count++;
                System.out.println("第" + i + "轮" + "第" + j + "次冒泡:" + Arrays.toString(a));
            }
//            System.out.println(i + "--" + Arrays.toString(a) + "--" + count);
            if (!isExchange) {
                break;
            }

        }

        return a;
    }


    /**
     * 参考Ai编写
     *
     * @param array 数组
     * @return 排序后的数组
     */
    private static int[] bubble(int[] array) {
        int length = array.length - 1;
        int count = 0;
        for (int i = 0; i < length - 1; i++) {
            boolean isExchange = false;
            //一轮冒泡
            for (int j = 0; j < length - i; j++) {
                if (array[j] > array[j + 1]) {
                    exchange(array, j);
                    isExchange = true;
                }
                count++;
            }
            if (!isExchange) {
                break;
            }
            System.out.println(i + "--" + Arrays.toString(array) + "--" + count);
        }
        return array;
    }

    private static void exchange(int[] array, int j) {
        int temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
    }
}
